package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-26
 */

/**
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 */
public class leetcode215 {
    public static void main(String[] args) {
        System.out.println("hello");
    }
    public int findKthLargest(int[] nums, int k) {
        nums = createHeap(nums);
        int N = nums.length-1;
        while (N!=nums.length-k){
            int tmp = nums[0];
            nums[0] = nums[N];
            nums[N] = tmp;

            N--;
            sink(nums,0,N);
        }
        return nums[0];
    }
    public int[] createHeap(int[] nums){
        for (int i = nums.length/2-1; i >= 0; i--) {
            sink(nums,i,nums.length-1);
        }
        return nums;
    }
    public void sink(int[] nums,int target,int range){
        while (2*target+1<=range){
            int max;
            if (2*target+2<=range){
                if (nums[2*target+1]<nums[2*target+2]) max = 2*target+2;
                else max = 2*target+1;
            }
            else max = 2*target+1;
            if (nums[target]>=nums[max]) break;

            int tmp = nums[target];
            nums[target] = nums[max];
            nums[max] = tmp;

            target = max;
        }
    }
}
